This chapter discusses in detail the binary tree objects included in the Containers Library. It describes how to use these objects and the different types of binary trees available.
In this chapter you will learn:
- What are binary trees and height balanced trees?
- How to use the binary trees and the AVL trees
- The characteristics of each type of binary tree
What are binary trees?
A binary tree is a special kind of tree that is either empty or has one node called the root, along with two binary trees called left subtree and right subtree. A binary search tree is a binary tree in which each node contains a key that satisfies the following conditions:
- All keys (if any) in the left subtree of the root precede the key of the root.
- The key in the root precedes all the keys (if any) in the right subtree.
- Both the left and right subtrees are binary search trees.
An AVL is a variation of a binary tree in which the height of its subtrees varies by not more than one level. That is, an AVL tree is what is called a height balanced tree. Since the tree is kept almost perfectly balanced, insertions and deletions are of the order of O(log n) in the worst case. If an insertion or deletion causes the tree to become too far out of balance, the tree is rebalanced.
Using the binary trees
There are two types of binary trees included in the library: a non-balanced version and a height balanced version (AVL). To use either of the trees, you must first create a data item, which must be a descendant of TBinaryNode or TAVLNode, depending on which tree you want to use. For example, if you want to use the non-balanced binary tree, you would make your object a descendant of TBinaryNode:
type
PContact = ^TContact;
TContact = object(TBinaryNode)
FirstName,
LastName,
Phone,
Company : PString;
constructor Init(ALastName, AFirstName, APhone,
ACompany : string);
function KeyOf : Pointer; virtual;
destructor Done; virtual;
end;
Since all graphs by default are sorted containers, you must override the KeyOf method, to let the graph know how you want to sort your data. As with linked lists, you must override the node's KeyOf method, instead of the tree's KeyOf method.
function TContact.KeyOf : Pointer;
begin
KeyOf := LastName;
end;
Once you have created the new TBinaryNode (or TAVLNode) descendant that will hold your data, you can use TGraph's and TContainer's methods to access the data in the trees. Two additional methods, Traverse and TraverseThat, let you traverse the trees in order, pre-order or post-order, and perform an action on some or all of the nodes in the tree.
Since data items are stored in memory at all times, the use of DoneItem is not required. However, if you intend to write data-structure independent applications, you must still always use it after retrieving an item from the container.
For complete examples on using the binary trees, see the files BiTrees1.PAS and BiTrees2.PAS.
